1. Technical Field
The invention relates to digital data, including digital audio, video, and image data. More particularly, the invention relates to a method and apparatus for embedding authentication data within such digital data in a way that avoids detection by a casual observer and that allows a user to determine whether the digital data have been modified from their intended form.
2. Description of the Prior Art
The number of applications that use digital storage and transmission techniques is increasing at a rapid rate. This technology currently has a broad range of uses, such as computer manipulation of audio, video and images; high-quality transmission of video over public networks (including cable and telephone networks);
and permanent storage of archival data, including optically scanned text and images, such as letters and documentation.
Digital data may be modified such that it is not possible to detect whether the digital data have been modified, without use of extraordinary means. For example, a photograph may be digitized with high-resolution scanning equipment. Once digitized, the photograph may be modified with any of several different commercial computer programs, and the modified photograph may then be printed with a high-resolution photographic printer. It is impossible to detect tampering with the photographic image by examining the image itself.
Similarly, audio and video recordings are also vulnerable to such electronic tampering.
Consider another case: the expanding use of optically scanned images of documentation to maintain an electronic database of business and/or legal records. For example, many insurance companies are converting to all electronic files. In fact, Federal government regulations now permit the destruction of paper documentation after conversion to an electronic format. Such scanned information is often of limited quality and of low resolution, making tampering a simple task.
The so-called information highway and other increasingly ubiquitous electronic distribution systems provide fertile grounds in which piracy and electronic tampering can flourish. For example, the Bernie convention on copyrights gives an artist the right to maintain his work as a single, complete, and unmodified whole. Electronic tampering makes it difficult to ensure and police this property right.
The following definitions are provided for purposes of the discussion herein:
xe2x80x9cAuthenticationxe2x80x9d refers to techniques that are used to avoid the problem of electronic tampering and similar problems. The specific effects authentication addresses are:
Known Creator. It is important that to know with assurance that the object originated with the proper source. For example, that a movie came directly from the studio.
No Tampering. It is important to have assurance that the object has not been modified in some way. For example, it is necessary to know that the movie is the same one paid for, with all portions intact.
Authority to Possess. The receiver of the object should be able to prove that the object was properly obtained (e.g. by licensing or purchase).
Authenticity can be proven either by some feature of the object itself, or by an accompanying object which is known to be authentic. For example, a license to use a copy of a software product, usually a paper document, typically accompanies the disks containing the software. However, tampering with the object is not easily detected. The software on the disks may have been modified, or the license itself may have been altered or forged.
Practitioners in communications technologies use the terms xe2x80x9cin-bandxe2x80x9d and xe2x80x9cout-of-bandxe2x80x9d to refer to methods for embedding additional, disguised data within the communications channel. In-band information is information that is carried within the transmission format itself, while out-of-band information is information that is carried outside the communications channel, e.g. via a second channel. Thus, in-band refers to data encoding that is transparent to underlying transmission and storage systems, while out-of-band refers to data encoding that is visible to transmission and storage systems because it must be handled directly. Authentication information can be carried either in-band or out-of-band.
An example of out-of-band information relates to the signaling necessary to set up a phone call between telephone exchanges. This signaling is usually carried on various links that are separate from those links that carry the data for the phone connection.
Data overlaid in-band are referred to as embedded data. Various television transmission systems embed data in-band without changing the format or viewability of the television signal, for example when providing close-captioning, time codes for video editing, and low-speed data transmission channels for cable converter control and other uses.
Embedded data are sometimes stored in specific fields reserved within a digital data stream. The size and format of these fields does not usually provide sufficient space, security, or reliability to allow the transmission of sensitive data, such as authentication information. It is also desirable to avoid changes to existing formats, and to avoid committing portions of future formats to always carry certain fields. It is therefore preferred to allow the embedding of data within a data stream independently of the stream format, such that the both embedded data and the original data stream (if desired) can be recovered in a reliable and secure fashion.
Embedding additional data in a digital data stream requires modification of the original data stream. If it is desired to restore the original data stream, the portion of the original data stream that was modified during the embedding process must be replaced with the original data. Accordingly, the original data must be embedded in the data stream along with the additional data. If high level information about the data stream structure is available, it may be possible to embed the additional data with less intrusion, such that the additional data are undetectable to the casual observer.
The term xe2x80x9cmeta-dataxe2x80x9d refers to information about the data stream, such as file permission, file type, application type, serial number, creator identification, licensee identification, and other arbitrary attributes of the data stream. It is important that meta-data are copied and distributed in precise tandem with the copying and distribution of the data stream. Out-of-band systems carry this meta-data as either separate parcels of information, or by reformatting the data stream.
An example of meta-data involves copying a data stream between two computer systems. An out-of-band system first copies the meta-data to a suitable file, or stores the information in a relational database. Following this, the original digital data are copied and stored in a separate file. Because multiple files require a file management scheme, there is a significant likelihood that the data stored in one file do not match the corresponding data in other files. An in-band meta-data system only has a single file, representing both the data stream and information about the data stream, avoiding the foregoing problems associated with out-of-band systems.
One of the most important aspects of meta-data is their use for higher-level authentication purposes. Ideally, meta-data should be stored as an in-band component of the digital data stream, making the stream simpler to handle and administer. Thus, an out-of-band scheme is not well suited for this application for at least the following reasons: First, movement of security data must be explicitly handled by the underlying transmission or storage system, adding cost and complexity to the system. Second, separate transmission or storage of such security information provides opportunities for unauthorized capture of the information, and for aliasing, i.e. where the correct information is suppressed and modified data are provided instead. Third, there is a likelihood of generating errors due to lost or misplaced security data.
In those applications that provide data authentication, a digital data stream must be permanently marked with embedded meta-data, such as a serial number or other identifying information, without altering the underlying data format. This makes it possible to distribute copies of the original data that include indelible authentication information, such that later certification of the copies or detection of unauthorized copying is possible.
One industry in which there is a need for such embedded authentication is the graphics design industry, and in particular companies that provide high quality, stock photographic images in digital format for use in connection with sales collateral and advertisements. These companies typically charge a royalty for each use of a photographic image. While the use of electronic distribution for photographic images is very attractive, because of its potential to lower distribution and inventory costs significantly, the ability to produce an infinite number of perfect copies of such images is a big danger to this industry, because there would be little control over distribution. The ability to verify that each copy of a particular photograph is authorized would prevent loss of revenue due to unauthorized copying by allowing ready identification of such unauthorized copies. Accordingly, embedded authentication data can provide a way both to detect illegal copying and to prove ownership.
The meta-data embedding process must be secure, otherwise the embedded information can be modified by unauthorized persons in much the same way that the data stream can be modified. The integrity of the data stream may be secured on several levels, but the most powerful form of such security only occurs if it is possible to verify that the digital data stream being checked is exactly the same as the original data stream, i.e. that the digital data stream and the authentication information carried in the data stream match, indicating that they have not been tampered with.
For this purpose, it is necessary to calculate a compact representation of a digital image from which it is extremely difficult or impossible to reproduce the original. This representation is referred to as a digital signature. A suitable algorithm for calculating a digital signature generates a representation that is not reproducible except from the original data. Examples of digital signatures include a checksum, which is good for small blocks of data; a cyclic redundancy check (CRC), which provides a much better signature over larger blocks of data; and a fast Fourier transform (FFT), which produces a family of polynomials describing the frequencies in the digital block (essentially, the FFT transforms data described in the spatial domain to the frequency domain).
It would be a significant advance in the art of electronic distribution if digital information could be secured against unauthorized use or copying, for example by providing a tamper proof authentication scheme.
The invention provides a method and apparatus for basic authentication of a digital block and for carrying additional authentication information provided by the user, i.e. meta-data, in a secure and reliable fashion. To embed authentication data into a digital block, a digital signature is formed that is a reduced representation of the digital block. The signature and additional information supplied by the user are embedded into the digital block by replacing predetermined bits within the block. Encryption can be used to enhance authentication capability. The encrypted data can be further verified using error correction coding techniques. For sequential data, such as the frames of a video display, a sequence numbers can also be provided as part of the meta-data to ensure that frames have not been deleted or re-ordered.
During authentication the foregoing steps are reversed, such that authentication can be performed only by one having knowledge of the precise coding procedure. A dedicated logic device can be used to enhance the performance of the foregoing operations.